//给定一个三角形 triangle ，找出自顶向下的最小路径和。 
//
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果
//正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 
//
// 示例 2： 
//
// 
//输入：triangle = [[-10]]
//输出：-10
// 
//
// 
//
// 提示： 
//
// 
// 1 <= triangle.length <= 200 
// triangle[0].length == 1 
// triangle[i].length == triangle[i - 1].length + 1 
// -10⁴ <= triangle[i][j] <= 10⁴ 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？ 
// 
// Related Topics 数组 动态规划 👍 1120 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * [P120]_三角形最小路径和
 * @author cjl
 * @date 2022-10-17 22:31:49
 */
public class P120_Triangle{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P120_Triangle().new Solution();
           List<Integer> t1 =new ArrayList<>();
           t1.add(2);
           List<Integer> t2 = new ArrayList<>();
           t2.add(3);
           t2.add(4);
           List<List<Integer>> list = new ArrayList<>();
           list.add(t1);
           list.add(t2);
           int result = solution.minimumTotal(list);
          System.out.println("args = " + result);
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          /**
           * min[i][j] 表示到达第i行j列元素最小值；
           * min[i][0] = sum(num[0][0]+ num[1][0]+……+num[i][0])
           * min[i][i] = sum(num[0][0]+ num[1][1] + ...+ num[i][i]);
           * min[i][j](i>0,j<i) = min(min[i-1][j-1],min[i-1][j])+num[i][j]
           * @param triangle
           */
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] minTotalArray = new int[triangle.size()][triangle.size()];
        minTotalArray[0][0] = triangle.get(0).get(0); //首位数
        for(int i = 1; i < triangle.size(); i++){
            for(int j = 0 ; j <= i; j++){
                if(i==j){
                    minTotalArray[i][i] = minTotalArray[i-1][i-1] + triangle.get(i).get(i);
                }else if(j== 0){
                    minTotalArray[i][0] = minTotalArray[i-1][0] + triangle.get(i).get(0);
                }else {
                    if(minTotalArray[i-1][j-1] > minTotalArray[i-1][j]){
                        minTotalArray[i][j] =  minTotalArray[i-1][j] + triangle.get(i).get(j);
                    }else{
                        minTotalArray[i][j] =  minTotalArray[i-1][j-1] + triangle.get(i).get(j);
                    }
                }
            }
        }

        return Arrays.stream(minTotalArray[triangle.size() - 1]).min().getAsInt();
    }

}
//leetcode submit region end(Prohibit modification and deletion)

  }